package leetcode.other.recursion;

import utils.Times;

/**
 * DESCRIPTION: https://leetcode.cn/problems/fibonacci-number/
 * Author: ammar
 * Date:   2021/12/7
 * Time:   下午3:01
 */
public class _509_斐波那锲数 {
    /**
     * 0 1 1 2 3 5
     * n = (n-1) + (n-2)
     */

    /**
     * 第一种方法 直接按公式做
     * @param n
     * @return
     */
    public static int fib1(int n) {
        if (n <= 1) return n;
        return fib1(n - 1) + fib1(n - 2);
    }

    /**
     * 第二种方法 找规律
     * 0 1 1 2 3 5
     * n = (n-1) + (n-2)
     * 观察：第一个数为0，第二个数为1
     * 第三个数 0 + 1，此时加法运算了1次
     * 第四个数 1 + 1，此时加法运算了2次
     * ...
     * 第n个数为 (n-1) + (n-2)，此时加了 n-2 次
     * @param n
     * @return
     */
    public static int fib2(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;
        int sum = 0;
        for (int i = 0; i <= n - 2; i++) {
            second = first + second;
            first = second - first;
        }
        return sum;
    }

    public static int fib3(int n) {
        return fib3(n, 1, 1);
    }

    // 斐波那契数列尾调用递归优化
    public static int fib3(int n, int first, int second) {
        if (n <= 1) return first;
        return fib3(n - 1, second, first + second);
    }


    public static void main(String[] args) {

        int n = 45;
        Times.test("fib2", () -> {
            System.out.println(fib2(n));
        }); // 0 秒
        Times.test("fib1", () -> {
            System.out.println(fib1(n));
        }); // 3.811 秒
    }
}
